package xiaomin.demo.algorithm;

public class QSort {
    public static void quickSort(int[] arr, int low, int high) {

        if (low < high) {
            // 找寻基准数据的正确索引
            int index = getIndex(arr, low, high);

            // 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
            //quickSort(arr, 0, index - 1); 之前的版本，这种姿势有很大的性能问题，谢谢大家的建议
            quickSort(arr, low, index - 1);
            quickSort(arr, index + 1, high);
        }
        else{
            //当low==high时停止递归
            return;
        }

    }

    //分区函数,找座位
    private static int getIndex(int[] arr, int low, int high) {
        // 基准数据为第一个数字
        int tmp = arr[low];
        int lowPointer=low;//低位指针
        int highPointer=high;//高位指针
        int direction=0;//0:从后往前 1：从前往后

        //方法1：一个循环
//        while (lowPointer<highPointer){
//            if(direction==0) {//从后往前
//                if (arr[highPointer] >= tmp) {
//                    highPointer--;
//                } else {//碰到比自己小的
//                    arr[lowPointer] = arr[highPointer];
//                    direction=1;
//                }
//            }
//            else {//从前往后
//                if(arr[lowPointer]<=tmp){
//                    lowPointer++;
//                }
//                else {
//                    arr[highPointer]=arr[lowPointer];
//                    direction=0;
//                }
//            }
//        }
        //方法2：嵌套循环
        while (lowPointer<highPointer){
            while (lowPointer<highPointer && arr[highPointer]>=tmp){
                highPointer--;
            }
            //发现比它小的数,交换
            arr[lowPointer]=arr[highPointer];

            while (lowPointer<highPointer && arr[lowPointer]<=tmp){
                lowPointer++;
            }
            //发现比它大的数,交换
            arr[highPointer]=arr[lowPointer];
        }

        arr[lowPointer]=tmp;

        return lowPointer;
    }
}
